namespace Apex
{
	//结点类
	template<class T>
	struct list_node
	{
		//成员变量
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		//成员函数

		//构造函数
		list_node(const T& data = T());
	};

	//迭代器类
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> iterator;

		//成员变量
		Node* _node;

		//成员函数

		//构造函数
		__list_iterator(Node* node);

		//解引用运算符重载
		Ref operator*();
		//成员访问符重载
		Ptr operator->();

		//前置++
		iterator& operator++();
		//后置++
		iterator operator++(int);
		//前置--
		iterator& operator--();
		//后置--
		iterator operator--(int);

		//关系运算符
		bool operator==(const iterator& it);
		bool operator!=(const iterator& it);
	};

	//链表类
	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:

		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		typedef __reverse_iterator<iterator, T&, T*> riterator;
		typedef __reverse_iterator<const_iterator, const T&, const T*> const_riterator;

		//成员函数

		//迭代器函数
		iterator begin();
		const_iterator begin() const;
		iterator end();
		const_iterator end() const;
		
		riterator rbegin();
		const_riterator rbegin() const;
		riterator rend();
		const_riterator rend() const;

		//无参构造函数
		list();
		//有参构造函数(初始化n个结点)
		list(size_t n, const T& val = T());
		//迭代器构造函数
		template<class InputIterator>
		list(InputIterator first, InputIterator last);

		//清空链表数据
		void clear();
		//析构函数
		~list();

		//拷贝构造
		list(const list<T>& lt);
		//赋值重载
		list<T>& operator=(list<T> lt);

		//pos前插入
		void insert(iterator pos, const T& x);
		//删除pos处数据
		iterator erase(iterator pos);

		//尾插
		void push_back(const T& x);
		//头插
		void push_front(const T& x);

		//尾删
		void pop_back();
		//头删
		void pop_front();

	private:
		Node* _head;
	};
}

